package week04;

public class T031 {
	//若只使用coins 中的前i个（i从1开始计数）硬币的面值，若想凑出金额j，有dp[i][j]种凑法。
	static int[][] dp =new int[9][201];
	public static void dp(int[] coins,int amount) {
		for(int i=0;i<=8;i++) dp[i][0]=1;
		for(int i=1;i<=8;i++) {
			for(int j=1;j<=200;j++) {
				if(j-coins[i-1]>=0) 
					dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]];
				else dp[i][j]=dp[i-1][j];
			}
		}
		System.out.println(dp[8][200]);
	}
	public static void main(String[] args) {
		int[] coins = {1,2,5,10,20,50,100,200};
		int amount = 200;
		dp(coins,amount);
	}
}
